The next automata model we will present is a restricted type of a
two-dimensional cellular automaton with the name two-dimensional online
tessellation automaton abbreviated as 2OTA. A cellular automaton is an array of
``cells" where each cell contains a pixel of the input picture and a state. The
automaton moves diagonally over the picture to compute the state of each cell.
After the computation, the automaton accepts a picture if the cell in the bottom
right corner is in an accepting state. The 2OTA was introduced by K. Inoue and A.
Nakamura in 1977(see~\cite{inoue1977acceptors}). 

In this automata model, each cell only receives its state at one step at a time.
Exactly at that moment when the two neighbours on the top and the left of a cell
$c$ have a defined state, $c$ can define its own state depending on its
symbol and the states of these neighbours.
\begin{definition} A \emph{deterministic two-dimensional online tessellation
automaton} abbreviated as 2DOTA is a 5-tuple $M = (Q, \Sigma, \delta, q_0, F)$,
where
\begin{compactitem}
	\item $Q$ is a finite set of states,
	\item $\Sigma$ is a finite set of input symbols,
	\item $q_0 \in Q$ is the set of initial states,
	\item $F \subseteq Q$ is the set of accepting states
	\item $\delta: Q \times Q \times \Sigma \rightarrow Q$ is the control function.
\end{compactitem}
\end{definition} 
The automaton $M$ starts at time step $t = 0$ on a picture $p \in \Sigma^{*,*}$.
At this time step, the initial state $q_0$ is associated to every position of the
first row and column of $\hat{p}$. One time step later, the top left corner of
$p$ associates the state $\delta(q_0, q_0, p(1, 1))$. At time step $t = 2$,
the position $p(1, 2)$ and $p(2, 1)$ define their states, and so on. That means
$M$ moves along the first main diagonal over the picture to define the state of
each cell which is parallel to the second main diagonal dependent on the
current position. The automaton $M$ accepts a picture $p$, if after the
computation an accepting state is associated to
position $(l_1(p), l_2(p))$.

Now we show an example of a 2DOTA. First let $S = \{p \mid p\in\Sigma^{*,*},
l_1(p) = l_2(p)\}$ be the language of all quadratic pictures over $\Sigma$. The
following definition of a 2DOTA $M$ is one possible construction such that $L(M)
= S$ holds.
\begin{example}
$M = (\{q_0, q_1, q_2, q_a\}, \{0\}, \delta, \{q_0\}, \{q_a\})$ \\
Remark that this table of transitions does not contain symbols because $M$
has a unary alphabet.
\begin{center}
\begin{tabular}{c|c|c|c|c}
$\delta$ & $q_0$ & $q_1$ & $q_2$ & $q_a$ \tabularnewline
\hline
$q_0$    & $q_a$ & -     & $q_2$ & $q_2$ \tabularnewline
\hline
$q_1$    & $q_1$ & $q_1$ & -     & -     \tabularnewline
\hline
$q_2$    & -     & $q_a$ & $q_2$ & $q_2$ \tabularnewline
\hline
$q_a$    & $q_1$ & $q_1$ & -     & -     \tabularnewline
\end{tabular}
\end{center}
\end{example}
$M$ associates the final state $q_a$ to every position in the first main
diagonal of an input picture $p$. For all positions in $p$ above the first main
diagonal $M$ associates the state $q_1$ and for all positions below the state
$q_2$. If, after the run of $M$, the final state $q_a$ is in the right bottom
corner, the input picture is a square. 

We now regard how $M$ will operate with the following picture $p \in S$.
\begin{center}
$p = $\begin{tabular}{|D{0.4cm}|D{0.4cm}|D{0.4cm}|}
\hline
0  & 0  & 0 \tabularnewline
\hline
0  & 0  & 0 \tabularnewline
\hline
0  & 0  & 0 \tabularnewline
\hline
\end{tabular}
$ \hat{p} = $\begin{tabular}{|D{0.4cm}|D{0.4cm}|D{0.4cm}|D{0.4cm}|D{0.4cm}|}
\hline
\# & \# & \# & \# & \# \tabularnewline
\hline
\# & 0  & 0  & 0  & \# \tabularnewline
\hline
\# & 0  & 0  & 0  & \# \tabularnewline
\hline
\# & 0  & 0  & 0  & \# \tabularnewline
\hline
\# & \# & \# & \# & \# \tabularnewline
\hline
\end{tabular}
\end{center}
First $M$ appends the initial state to all cells of the first row and first
column of $\hat{p}$. The following time steps should be self-explanatory.
\begin{center}
$\overset{t = 0}{\rightarrow}$
\begin{tabular}{|B{0.7cm}|B{0.7cm}|B{0.7cm}|B{0.7cm}|B{0.7cm}|}
\hline
\#$q_0$ & \#$q_0$ & \#$q_0$ & \#$q_0$ & \#$q_0$ \tabularnewline
\hline
\#$q_0$ & 0       & 0       & 0       & \#      \tabularnewline
\hline
\#$q_0$ & 0       & 0       & 0       & \#      \tabularnewline
\hline
\#$q_0$ & 0       & 0       & 0       & \#      \tabularnewline
\hline
\#$q_0$ & \#      & \#      & \#      & \#      \tabularnewline
\hline
\end{tabular}
$\overset{t = 1}{\rightarrow}$
\begin{tabular}{|B{0.7cm}|B{0.7cm}|B{0.7cm}|B{0.7cm}|B{0.7cm}|}
\hline
\#$q_0$ & \#$q_0$ & \#$q_0$ & \#$q_0$ & \#$q_0$ \tabularnewline
\hline
\#$q_0$ & 0$q_a$  & 0       & 0       & \#      \tabularnewline
\hline
\#$q_0$ & 0       & 0       & 0       & \#      \tabularnewline
\hline
\#$q_0$ & 0       & 0       & 0       & \#      \tabularnewline
\hline
\#$q_0$ & \#      & \#      & \#      & \#      \tabularnewline
\hline
\end{tabular}
\end{center}
\begin{center}
$\overset{t = 2}{\rightarrow}$
\begin{tabular}{|B{0.7cm}|B{0.7cm}|B{0.7cm}|B{0.7cm}|B{0.7cm}|}
\hline
\#$q_0$ & \#$q_0$ & \#$q_0$ & \#$q_0$ & \#$q_0$ \tabularnewline
\hline
\#$q_0$ & 0$q_a$  & 0$q_1$  & 0       & \#      \tabularnewline
\hline
\#$q_0$ & 0$q_2$  & 0       & 0       & \#      \tabularnewline
\hline
\#$q_0$ & 0       & 0       & 0       & \#      \tabularnewline
\hline
\#$q_0$ & \#      & \#      & \#      & \#      \tabularnewline
\hline
\end{tabular}
$\overset{t = 3}{\rightarrow}$
\begin{tabular}{|B{0.7cm}|B{0.7cm}|B{0.7cm}|B{0.7cm}|B{0.7cm}|}
\hline
\#$q_0$ & \#$q_0$ & \#$q_0$ & \#$q_0$ & \#$q_0$ \tabularnewline
\hline
\#$q_0$ & 0$q_a$  & 0$q_1$  & 0$q_1$  & \#      \tabularnewline
\hline
\#$q_0$ & 0$q_2$  & 0$q_a$  & 0       & \#      \tabularnewline
\hline
\#$q_0$ & 0$q_2$  & 0       & 0       & \#      \tabularnewline
\hline
\#$q_0$ & \#      & \#      & \#      & \#      \tabularnewline
\hline
\end{tabular}
\end{center}
\begin{center}
$\overset{t = 4}{\rightarrow}$
\begin{tabular}{|B{0.7cm}|B{0.7cm}|B{0.7cm}|B{0.7cm}|B{0.7cm}|}
\hline
\#$q_0$ & \#$q_0$ & \#$q_0$ & \#$q_0$ & \#$q_0$ \tabularnewline
\hline
\#$q_0$ & 0$q_a$  & 0$q_1$  & 0$q_1$  & \#      \tabularnewline
\hline
\#$q_0$ & 0$q_2$  & 0$q_a$  & 0$q_1$  & \#      \tabularnewline
\hline
\#$q_0$ & 0$q_2$  & 0$q_2$  & 0       & \#      \tabularnewline
\hline
\#$q_0$ & \#      & \#      & \#      & \#      \tabularnewline
\hline
\end{tabular}
$\overset{t = 5}{\rightarrow}$
\begin{tabular}{|B{0.7cm}|B{0.7cm}|B{0.7cm}|B{0.7cm}|B{0.7cm}|}
\hline
\#$q_0$ & \#$q_0$ & \#$q_0$ & \#$q_0$ & \#$q_0$ \tabularnewline
\hline
\#$q_0$ & 0$q_a$  & 0$q_1$  & 0$q_1$  & \#      \tabularnewline
\hline
\#$q_0$ & 0$q_2$  & 0$q_a$  & 0$q_1$  & \#      \tabularnewline
\hline
\#$q_0$ & 0$q_2$  & 0$q_2$  & 0$q_a$  & \#      \tabularnewline
\hline
\#$q_0$ & \#      & \#      & \#      & \#      \tabularnewline
\hline
\end{tabular}
\end{center}
We can see that after five time steps $M$ has finished its run over $p$. Note
that every computation of a 2OTA consists of $l_1(p) + l_2(p) - 1$ steps.

Now we can talk about the closure properties. The proofs of the following
theorems can be found in~\cite{inoue1977acceptors}.
\begin{theorem} 
$\familyOf{2OTA}$ is closed under projection, concatenation and closure
operations.
\end{theorem}
Regarding to the language family dependecies we can say that the
non-deterministic 2OTA's accept more languages than the determistic ones.
K. Inoue and A. Nakamura have proved the following theorem.
\begin{theorem} 
$\familyOf{2DOTA} \subset \familyOf{2NOTA}$.
\end{theorem}
In~\cite{inoue1977acceptors} it was also proved that the
2NOTA is more powerful than the 4NFA and the deterministic versions are
incomparable under inclusion.
\begin{theorem}
$\familyOf{4NFA} \subset \familyOf{2NOTA}$, \\
$\familyOf{4DFA}$ and $\familyOf{2DOTA}$ are incomparable.
\end{theorem}
More information about this type of model you can find
in~\cite{giammarresi1997twodimensional}.
\label{ota}